The present invention relates to a low density parity check (LDPC) codes decoder and a method thereof. The present invention is adapted to deal with LDPC codes with various coding rates by the same configuration. The present invention is also adapted to improve processing throughput without degrading the quality.    Document 1: R. G. Gallager, “Low-Density Parity-Check Codes”, IRE Trans. Info. Theory, vol. IT-8, pp. 21-28, 1962    Document 2: A. J. Blanksby and C. J. Howland, “A 690-mW 1-Gb/s 1024-b, Rate-1/2 Low-Density Parity-Check Code Decoder,” IEEE J. Solid-State Circuits, vol. 37, pp. 404-412, March 2002    Document 3: Y. Chen and D. Hocevar, “A FPGA and ASIC Implementation of Rate 1/2, 8088-b Irregular Low Density Parity Check Decoder,” IEEE GLOBECOM2003, pp. 113-117, 2003    Document 4: M. M. Mansour and N. R. Shanbhag, “High-Throughput LDPC Decoder,” IEEE Trans. VLSI Systems, vol. 11, No. 6, December 2003
As a decoding algorithm for LDPC codes, a Belief Propagation (BP) algorithm is known (refer to Document 1). The BP algorithm is a belief propagation algorithm in which the reliability is updated by iterating the row processing (check node processing) shown in Equations (1) to (3) and the column processing (variable node processing) shown in Equations (4) and (5) (refer to Document 3). Meanwhile, Equations (4) and (5) are combined into Equation (6):
[Row Processing]Lmni=Zni-1−Rmni-1  (1)
                              R          mn          i                =                              {                                          ∐                                  j                  ∈                                                            A                      ⁡                                              (                        m                        )                                                              ⁢                                          \                      ⁢                      n                                                                                  ⁢                                                          ⁢                              Sign                ⁡                                  (                                      L                    mj                    i                                    )                                                      }                    [                                    -              ψ                        ⁢                          {                                                ∑                                      j                    ∈                                                                  A                        ⁡                                                  (                          m                          )                                                                    ⁢                                              \                        ⁢                        n                                                                                            ⁢                                  ψ                  ⁡                                      (                                          L                      mj                      i                                        )                                                              }                                ]                                    (        2        )            ψ(x)=1n(tan h(|x/2|))  (3)
[Column Processing]
                              S          n          i                =                              ∑                          m              ∈                              B                ⁡                                  (                  n                  )                                                              ⁢                      R            mn            i                                              (        4        )            Zni=Fn+Sni  (5)
[Column Processing]
                              Z          n          i                =                              F            n                    +                                    ∑                              m                ∈                                  B                  ⁡                                      (                    n                    )                                                                        ⁢                          R              mn              i                                                          (        6        )            where i is the number of times of decoding iteration, Zin is a log likelihood ratio (LLR) after decoding processing has been executed i times at the nth bit, Fn is a channel data, and Rimn is a row processing result after decoding processing has been executed i times at the nth bit on row m (initial values Z0n=Fn, R0mn=0).
In Document 2, in which an architecture for a decoder applying the BP algorithm is shown, it has been reported that a throughput of 1 Gb/s at the maximum can be achieved by adopting a design for executing fully parallel processing of row processing and column processing (fully parallel design) at the time of decoding an LDPC code with a code length of 1024 bits and R=1/2. However, in such a design, LDPC codes with different check matrices cannot be decoded.
On the other hand, a Structured LDPC code is an LDPC code consisting of a base matrix (basic check matrix) of Mb rows and Nb columns and a permutation matrix of R rows and R columns (refer to FIG. 4 described later), and by changing the permutation matrix size R, it is possible to form check matrices for codes with different code lengths. By using a zero matrix or a cyclic shift matrix as a permutation matrix and holding only information on Mb×Nb shift values, locations of 1 on the check matrix can be identified easily. In Document 3, a decoder using the Structured LDPC code (hereinafter referred to as a structured LDPC code) is reported, and codes with different code lengths can be decoded due to the configuring method of the reported decoder.
Each of the LDPC codes with different coding rates has the different number of rows, different number of columns, and different number of variable node degrees.
In the configuring method of the decoder proposed in Document 3, LDPC codes with different coding rates cannot be decoded without changing the circuit configuration.
Also, in the decoding method to which the BP algorithm has been applied, the LLR is adapted to be updated per decoding iteration as shown in the above equations.
On the other hand, the Turbo Decoding Message Passing (TDMP) algorithm shown in Document 4 is an algorithm in which i in aforementioned Equations (1) to (4) is not the number of times of decoding iteration but time (cycle) when the mth row is processed. That is, the LLR is updated per row processing. Since the TDMP algorithm is excellent in convergence characteristics, it is known that it obtains equivalent error characteristics with less number of times of iteration than the BP algorithm's.
However, in the TDMP algorithm, when a row is to be processed, the row cannot be processed until the processing of a row and a column containing the same bit node as one contained in the target row is completed.
Also, in the TDMP algorithm as well, decoding processing is executed as many times of iteration as set before the decoding processing is terminated. However, in a case where there are inherently few errors, decoding processing executed predetermined times of iteration may be in vain.
Further, when error detection is to be executed, it needs to be done while the decoding processing is interrupted. This causes a problem in which the decoding processing is delayed as much as it takes for the error detection processing, and in which the error detection processing cannot be done frequently.